{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Replace All ?'s to Avoid Consecutive Repeating Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: modifyString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #替换所有的问号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个仅包含小写英文字母和 <code>'?'</code> 字符的字符串 <code>s</code>，请你将所有的 <code>'?'</code> 转换为若干小写字母，使最终的字符串不包含任何 <strong>连续重复</strong> 的字符。</p>\n",
    "\n",
    "<p>注意：你 <strong>不能</strong> 修改非 <code>'?'</code> 字符。</p>\n",
    "\n",
    "<p>题目测试用例保证 <strong>除</strong> <code>'?'</code> 字符 <strong>之外</strong>，不存在连续重复的字符。</p>\n",
    "\n",
    "<p>在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"?zs\"\n",
    "<strong>输出：</strong>\"azs\"\n",
    "<strong>解释：</strong>该示例共有 25 种解决方案，从 \"azs\" 到 \"yzs\" 都是符合题目要求的。只有 \"z\" 是无效的修改，因为字符串 \"zzs\" 中有连续重复的两个 'z' 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ubv?w\"\n",
    "<strong>输出：</strong>\"ubvaw\"\n",
    "<strong>解释：</strong>该示例共有 24 种解决方案，只有替换成 \"v\" 和 \"w\" 不符合题目要求。因为 \"ubvvw\" 和 \"ubvww\" 都包含连续重复的字符。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p><code>1 &lt;= s.length&nbsp;&lt;= 100</code></p>\n",
    "\t</li>\n",
    "\t<li>\n",
    "\t<p><code>s</code> 仅包含小写英文字母和 <code>'?'</code> 字符</p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [replace-all-s-to-avoid-consecutive-repeating-characters](https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [replace-all-s-to-avoid-consecutive-repeating-characters](https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"?zs\"', '\"ubv?w\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s=list(\"1\"+s+\"1\")\n",
    "        a=(\"a\",\"b\",\"c\")\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i]==\"?\":\n",
    "                for j in range(3):\n",
    "                    if  i>0 and i<len(s)-1 and s[i-1]!=a[j] and s[i+1]!=a[j]:\n",
    "                        s[i]=a[j]\n",
    "        s=s[1:-1]           \n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s=list(\"1\"+s+\"1\")\n",
    "        a=(\"a\",\"b\",\"c\")\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i]==\"?\":\n",
    "                for j in range(3):\n",
    "                    if  i>0 and i<len(s)-1 and s[i-1]!=a[j] and s[i+1]!=a[j]:\n",
    "                        s[i]=a[j]\n",
    "        s=s[1:-1]           \n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i]== \"?\":\n",
    "                for ch in \"abc\":\n",
    "                    if not (i > 0 and s[i-1]==ch or i < len(s)-1 and s[i+1]==ch):\n",
    "                        s[i] = ch\n",
    "                        break\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s=list(\"1\"+s+\"1\")\n",
    "        a=(\"a\",\"b\",\"c\")\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i]==\"?\":\n",
    "                for j in range(3):\n",
    "                    if  i>0 and i<len(s)-1 and s[i-1]!=a[j] and s[i+1]!=a[j]:\n",
    "                        s[i]=a[j]\n",
    "        s=s[1:-1]           \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        if length == 1:\n",
    "            if s[0] != \"?\":\n",
    "                return s\n",
    "            else:\n",
    "                s = 'a'\n",
    "                return s \n",
    "        if s[0] == \"?\":\n",
    "            if s[1] != 'a':\n",
    "                s = 'a'+s[1:]\n",
    "            else:\n",
    "                s = 'b'+s[1:]\n",
    "        if s[-1] == \"?\":\n",
    "            if s[-2] != 'a':\n",
    "                s = s[:-1]+'a'\n",
    "            else:\n",
    "                s = s[:-1]+'b'\n",
    "        for i in range(1,length-1):\n",
    "            if s[i] == '?':\n",
    "                if 'a' not in s[i-1:i+2]:\n",
    "                    s = s[:i] + 'a' + s[i+1:]\n",
    "                elif 'b' not in s[i-1:i+2]:\n",
    "                    s = s[:i] + 'b' + s[i+1:]\n",
    "                else:\n",
    "                    s = s[:i] + 'c' + s[i+1:]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s=list(\"1\"+s+\"1\")\n",
    "        a=(\"a\",\"b\",\"c\")\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i]==\"?\":\n",
    "                for j in range(3):\n",
    "                    if  i>0 and i<len(s)-1 and s[i-1]!=a[j] and s[i+1]!=a[j]:\n",
    "                        s[i]=a[j]\n",
    "        s=s[1:-1]           \n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        re = list(s)\n",
    "        n = len(re)\n",
    "        for i in range(n):\n",
    "            if re[i] == \"?\":\n",
    "                for b in \"abc\":\n",
    "                    if not (i > 0 and re[i - 1] == b or i < n -1 and re[i + 1] == b):\n",
    "                        re[i] = b\n",
    "                        break\n",
    "        return \"\".join(re)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        res = list(s)\n",
    "        n = len(res)\n",
    "        for i in range(n):\n",
    "            if res[i] == \"?\":\n",
    "                for b in \"uvw\":\n",
    "                    # 判断前后两个元素都不为这三个字母中的一个，则将该？替换为这个。同时要注意数组下标是否越界\n",
    "                    if  not ( i > 0 and res[i - 1] == b or i < n - 1 and res[i + 1] == b):\n",
    "                        res[i] = b\n",
    "                        break\n",
    "        return ''.join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        r = []\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        if n == 0: return r\n",
    "        for i in range(n):\n",
    "            if s[i] != \"?\":\n",
    "                r.append(s[i])\n",
    "            else:\n",
    "                if n == 1: return \"a\"\n",
    "                if i == 0:\n",
    "                    if s[1] == \"a\":\n",
    "                        r.append(\"b\")\n",
    "                    else:\n",
    "                        r.append(\"a\")\n",
    "                elif i == n-1:\n",
    "                    if r[-1] == \"a\":\n",
    "                        r.append(\"b\")\n",
    "                    else:\n",
    "                        r.append(\"a\")\n",
    "                else:\n",
    "                    if r[i-1] == \"a\":\n",
    "                        if s[i+1] == \"b\":\n",
    "                            r.append(\"c\")\n",
    "                        else:\n",
    "                            r.append(\"b\")\n",
    "                    elif r[i-1] == \"b\":\n",
    "                        if s[i+1] == \"a\":\n",
    "                            r.append(\"c\")\n",
    "                        else:\n",
    "                            r.append(\"a\")\n",
    "                    else:\n",
    "                        if s[i+1] == \"a\":\n",
    "                            r.append(\"b\")\n",
    "                        else:\n",
    "                            r.append(\"a\")  \n",
    "        return \"\".join(r)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s=list(\"1\"+s+\"1\")\n",
    "        a=(\"a\",\"b\",\"c\")\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i]==\"?\":\n",
    "                for j in range(3):\n",
    "                    if  i>0 and i<len(s)-1 and s[i-1]!=a[j] and s[i+1]!=a[j]:\n",
    "                        s[i]=a[j]\n",
    "        s=s[1:-1]           \n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        if len(s) == 1 and s == \"?\":\n",
    "            return \"t\"\n",
    "        elif len(s) == 1 and s != \"?\":\n",
    "            return s\n",
    "        s = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"?\":\n",
    "                for k in \"ufo\":\n",
    "                    if (i == 0 and k != s[1]) or (i == len(s)-1 and k != s[-2]) or (k != s[i-1] and k != s[i+1]):\n",
    "                        s[i] = k\n",
    "                        break\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "      ans = []\n",
    "      for i in range(len(s)):\n",
    "        if s[i] == \"?\":\n",
    "          for j in range(26):\n",
    "            ch = ord(\"a\") + j\n",
    "            if ans and ch == ord(ans[-1]):\n",
    "              continue\n",
    "            if i < len(s) - 1 and ch == ord(s[i+1]):\n",
    "              continue\n",
    "            ans.append(chr(ch))\n",
    "            break\n",
    "        else:\n",
    "          ans.append(s[i])\n",
    "      return \"\".join(ans) \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        letter=[chr(i) for i in range(97,123)]\n",
    "        n=len(s)\n",
    "        if n==1:\n",
    "            s='a'\n",
    "        for i in range(n):\n",
    "            if s[i]=='?':\n",
    "                if i>0 and i<n-1:\n",
    "                    for l in letter:\n",
    "                        if l!=s[i+1] and l!=s[i-1]:\n",
    "                            break\n",
    "                elif i==0:\n",
    "                    for l in letter:\n",
    "                        if l!=s[i+1]:\n",
    "                            break\n",
    "                else:\n",
    "                    for l in letter:\n",
    "                        if l!=s[i-1]:\n",
    "                            break\n",
    "                \n",
    "                s=s[:i]+l+s[i+1:]\n",
    "           \n",
    "        return s\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s = '0' + s + '0'\n",
    "        n = len(s)\n",
    "        res = '0'\n",
    "        d = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']\n",
    "        for i in range(1,n-1):\n",
    "            if s[i] == '?':\n",
    "                for k in d:\n",
    "                    if k != res[i-1] and k != s[i+1]:\n",
    "                        res += k\n",
    "                        break\n",
    "            else:\n",
    "                res += s[i]\n",
    "        return res[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == \"?\":\n",
    "                left_chr = s[i-1] if i >= 1 else \"\"\n",
    "                right_chr = s[i+1] if i <= n-2 else \"\"\n",
    "                used_chr = [left_chr, right_chr]\n",
    "                for j in range(26):\n",
    "                    c = chr(ord('a')+j)\n",
    "                    if c not in used_chr:\n",
    "                        s[i] = c\n",
    "                        break\n",
    "        return \"\".join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        \n",
    "        ans=\"\"\n",
    "        n=len(s)\n",
    "        if n==1:\n",
    "            if s==\"?\":\n",
    "                return \"a\"\n",
    "            else:\n",
    "                return s\n",
    "        for i in range(0,len(s)):\n",
    "            if s[i]!=\"?\":\n",
    "                ans=ans+s[i]\n",
    "            else:\n",
    "                if (i==0 and s[1]!=\"a\") or (i==n-1 and ans[i-1]!=\"a\") or (0<i<n-1 and ans[i-1]!=\"a\" and s[i+1]!=\"a\"):\n",
    "                    ans=ans+\"a\"\n",
    "                elif( 0<i<n-1 and ans[i-1]!=\"b\" and s[i+1]!=\"b\"):\n",
    "                    ans=ans+\"b\"\n",
    "                else:\n",
    "                    ans=ans+\"c\"\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        res = list(s)\n",
    "        n = len(res)\n",
    "        for i in range(n):\n",
    "            if res[i] == '?':\n",
    "                for b in \"abc\":\n",
    "                    if not (i > 0 and res[i - 1] == b or i < n - 1 and res[i + 1] == b):\n",
    "                        res[i] = b\n",
    "                        break\n",
    "        return ''.join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        res = list(s)\n",
    "        for i in range(len(res)):\n",
    "            if res[i] == '?':\n",
    "                for ch in 'abc':\n",
    "                    if not ((i > 0 and res[i - 1] == ch) or (i < len(res) - 1 and res[i + 1] == ch)):\n",
    "                        res[i] = ch\n",
    "                        break\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        if length == 1:\n",
    "            if s[0] != \"?\":\n",
    "                return s\n",
    "            else:\n",
    "                s = 'a'\n",
    "                return s \n",
    "        if s[0] == \"?\":\n",
    "            if s[1] != 'a':\n",
    "                s = 'a'+s[1:]\n",
    "            else:\n",
    "                s = 'b'+s[1:]\n",
    "        if s[-1] == \"?\":\n",
    "            if s[-2] != 'a':\n",
    "                s = s[:-1]+'a'\n",
    "            else:\n",
    "                s = s[:-1]+'b'\n",
    "        for i in range(1,length-1):\n",
    "            if s[i] == '?':\n",
    "                if 'a' not in s[i-1:i+2]:\n",
    "                    s = s[:i] + 'a' + s[i+1:]\n",
    "                elif 'b' not in s[i-1:i+2]:\n",
    "                    s = s[:i] + 'b' + s[i+1:]\n",
    "                else:\n",
    "                    s = s[:i] + 'c' + s[i+1:]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "\n",
    "        s = \" \"+s+\" \"\n",
    "        for index in range(1, len(s)-1):\n",
    "            if s[index] == \"?\" and s[index] != \" \":\n",
    "                for c in [\"a\", \"b\", \"c\"]:\n",
    "                    if s[index-1] != c and s[index+1] != c:\n",
    "                        s = s.replace(\"?\", c, 1)\n",
    "                        break\n",
    "        return s[1: -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        if s=='?':\n",
    "            return 'a'\n",
    "        else:\n",
    "            c= ['a', 'b', 'c']\n",
    "            t='a'\n",
    "            for i in range(len(s)):\n",
    "                if s[i] != '?':\n",
    "                    t+=s[i]\n",
    "                else:\n",
    "                    for j in c:\n",
    "                        if i==0 and j!=s[i+1]:\n",
    "                            t+=j\n",
    "                            break\n",
    "                        elif i==len(s)-1 and j!=t[-1]:\n",
    "                            t+=j\n",
    "                            break\n",
    "                        elif j != t[-1] and j != s[i+1]:\n",
    "                            t+=j\n",
    "                            break\n",
    "            return t[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '?':\n",
    "                for j in range(26):\n",
    "                    ch = ord('a') + j\n",
    "                    if ans and ch == ord(ans[-1]):\n",
    "                        continue\n",
    "                    if i < len(s)-1 and ch == ord(s[i+1]):\n",
    "                        continue\n",
    "                    ans.append(chr(ch))\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(s[i])\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        if len(s) == 1:\n",
    "            s = 'a'\n",
    "            return s\n",
    "        a = 'abc'\n",
    "        s = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if i == 0 and s[i] == '?':\n",
    "                for j in a:\n",
    "                    if j != s[i+1]:\n",
    "                        s[i] = j \n",
    "                        break\n",
    "            elif i == len(s)-1 and s[i] == '?':\n",
    "                for j in a:\n",
    "                    if j != s[i-1]:\n",
    "                        s[i] = j\n",
    "                        break\n",
    "            elif i != 0 and i != len(s)-1 and s[i] == '?':\n",
    "                for j in a:\n",
    "                    if j != s[i-1] and j != s[i+1]:\n",
    "                        s[i] = j\n",
    "                        break\n",
    "        ''.join(s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        alph = [chr(ord('a')+i) for i in range(26)]\n",
    "        dict1 = {key:0 for key in alph}\n",
    "        for i in range(len(s)):\n",
    "            if dict1.get(s[i])==0:\n",
    "                dict1[s[i]]=1\n",
    "        list1 = [key for key,value in dict1.items() if value==0]\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='?':\n",
    "                s[i]=list1.pop(0)\n",
    "                list1.append(s[i])\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        res = list(s)\n",
    "        n = len(res)\n",
    "        for i in range(n):\n",
    "            if res[i] == '?':\n",
    "                for b in \"abc\":\n",
    "                    if not (i > 0 and res[i - 1] == b or i < n - 1 and res[i + 1] == b):\n",
    "                        res[i] = b\n",
    "                        break\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        ad=[chr(x) for x in range(97,97+26)]        \n",
    "        #x=chr(97+int(random.random()*26))        \n",
    "        sl=[x for x in s]\n",
    "        for i in range(len(sl)):\n",
    "            if sl[i]=='?':\n",
    "                if i-1>=0 and sl[i-1] in ad:\n",
    "                    ad.remove(sl[i-1])\n",
    "                if i+1<len(sl) and sl[i+1] in ad:\n",
    "                    ad.remove(sl[i+1])\n",
    "                sl[i]=ad[0]\n",
    "                if i-1>=0 and sl[i-1] not in ad:\n",
    "                    ad.append(sl[i-1])\n",
    "                if i+1<len(sl) and sl[i+1] not in ad:\n",
    "                    ad.append(sl[i+1])                \n",
    "        return ''.join(sl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        l = 'abc'\n",
    "        s = '*'+s+'*'\n",
    "        ls = list(s)\n",
    "        for i in range(1,len(ls)-1):\n",
    "            if ls[i] == '?':\n",
    "                for j in l:\n",
    "                    if j != ls[i-1] and j != ls[i+1]:\n",
    "                        ls[i] = j\n",
    "        return ''.join(ls)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        res = list('d'+s+'d')\n",
    "        for i in range(1, len(res)-1):\n",
    "            if res[i]=='?':\n",
    "                for t in 'abc':\n",
    "                    if t not in res[i-1:i+2]:\n",
    "                        res[i] = t\n",
    "                        break\n",
    "        return ''.join(res[1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        if s=='?':\n",
    "            return 'a'\n",
    "        lst = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']\n",
    "        s = list(s)\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i]=='?':\n",
    "                for j in lst:\n",
    "                    if j!=s[i-1] and j!=s[i+1]:\n",
    "                        s[i]=j\n",
    "                        break\n",
    "        if s[0]=='?':\n",
    "            for j in lst:\n",
    "                if j!=s[1]:\n",
    "                    s[0]=j\n",
    "                    break\n",
    "        if s[-1]=='?':\n",
    "            for j in lst:\n",
    "                if j!=s[-2]:\n",
    "                    s[-1]=j\n",
    "                    break\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        lst = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if lst[i]=='?':\n",
    "                for j in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    if (i==0 or lst[i-1]!=j) and (i==len(lst)-1 or lst[i+1]!=j):\n",
    "                        lst[i]=j\n",
    "                        break\n",
    "        return ''.join(lst)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        index = 0\n",
    "        while '?' in s:\n",
    "            index = s.find('?', index)\n",
    "            if index > 0 and index < len(s) - 1:\n",
    "                for j in [chr(ord('a') + x) for x in range(26)]:\n",
    "                    if j != s[index - 1] and j != s[index + 1]:\n",
    "                        s = s[:index] + j + s[index + 1:]\n",
    "                        break\n",
    "            elif index == 0 and index == len(s) - 1:\n",
    "                s=\"a\"\n",
    "            elif index == 0:\n",
    "                for j in [chr(ord('a') + x) for x in range(26)]:\n",
    "                    if j != s[index + 1]:\n",
    "                        s = s[:index] + j + s[index + 1:]\n",
    "                        break\n",
    "            elif index == len(s) - 1:\n",
    "                for j in [chr(ord('a') + x) for x in range(26)]:\n",
    "                    if j != s[index - 1]:\n",
    "                        s = s[:index] + j + s[index + 1:]\n",
    "                        break\n",
    "        return s\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "alphabets = set(list('abcdefghijklmnopqrstuvwxyz'))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i] == '?':\n",
    "                exclude = set()\n",
    "                if (pre := i - 1) >= 0:\n",
    "                    exclude.add(s[pre])\n",
    "                if (follow := i + 1) < length:\n",
    "                    exclude.add(s[follow])\n",
    "                print(exclude)\n",
    "                if i + 1 < length:\n",
    "                    s = s[:i] + (alphabets - exclude).pop() + s[i + 1:]\n",
    "                else:\n",
    "                    s = s[:i] + (alphabets - exclude).pop()\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s_ = list(s)\n",
    "        n = len(s_)\n",
    "        for i in range(n):\n",
    "            if s_[i] == \"?\":\n",
    "                for ch in \"abc\":\n",
    "                    if not(i > 0 and s_[i-1] == ch or i < n-1 and s_[i+1] == ch):\n",
    "                        s_[i] = ch \n",
    "                        break\n",
    "        return \"\".join(s_)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        chars = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        lst = list(\"0\" + s + \"0\")\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            if lst[i] == \"?\":\n",
    "                j = 0\n",
    "                while chars[j] == lst[i - 1] or chars[j] == lst[i + 1]:\n",
    "                    j += 1\n",
    "                lst[i] = chars[j]\n",
    "            i += 1\n",
    "        return \"\".join(lst[1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        pre=list(s)\n",
    "        n=len(pre)\n",
    "        for i in range(n-1):\n",
    "            if pre[i]=='?':\n",
    "                for b in 'xyz':\n",
    "                    if b!=pre[i-1] and b != pre[i+1]:\n",
    "                        pre[i]=b\n",
    "                        break\n",
    "        if pre[n-1]=='?':\n",
    "            for b in 'xy':\n",
    "                if b!=pre[n-2]:\n",
    "                    pre[n-1]=b\n",
    "                    break\n",
    "                 \n",
    "        return ''.join(pre)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "alphabets = set(list('abcdefghijklmnopqrstuvwxyz'))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i] == '?':\n",
    "                exclude = set()\n",
    "                if i - 1 >= 0:\n",
    "                    exclude.add(s[i-1])\n",
    "                if i + 1 < length:\n",
    "                    exclude.add(s[i+1])\n",
    "                print(exclude)\n",
    "                if i + 1 < length:\n",
    "                    s = s[:i] + (alphabets - exclude).pop() + s[i + 1:]\n",
    "                else:\n",
    "                    s = s[:i] + (alphabets - exclude).pop()\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        l = 'abc'\n",
    "        s = '*'+s+'*'\n",
    "        ls = list(s)\n",
    "        for i in range(1,len(ls)-1):\n",
    "            if ls[i] == '?':\n",
    "                for j in l:\n",
    "                    if j != ls[i-1] and j != ls[i+1]:\n",
    "                        ls[i] = j\n",
    "        return ''.join(ls)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        res = list(s)\n",
    "        n = len(res)\n",
    "        for i in range(n):\n",
    "            if res[i] == '?':\n",
    "                for b in \"abc\":\n",
    "                    if not (i > 0 and res[i - 1] == b or i < n - 1 and res[i + 1] == b):\n",
    "                        res[i] = b\n",
    "                        break\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s1= 'abcdefghijklmnopqrstuvwxyz'\n",
    "        res = list('0'+s+'0')\n",
    "        i=1       \n",
    "        while i<len(res)-1:\n",
    "            if res[i]=='?':\n",
    "                j=0\n",
    "                while j<len(s1):\n",
    "                    if s1[j] not in [res[i-1],res[i+1]]:\n",
    "                        res[i]=s1[j]\n",
    "                        break\n",
    "                    j+=1\n",
    "            i+=1\n",
    "        return ''.join(res[1:-1])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        chars = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        lst = list(\"0\" + s + \"0\")\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            if lst[i] == \"?\":\n",
    "                j = 0\n",
    "                while chars[j] == lst[i - 1] or chars[j] == lst[i + 1]:\n",
    "                    j += 1\n",
    "                lst[i] = chars[j]\n",
    "            i += 1\n",
    "        return \"\".join(lst[1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        letters = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "        if n == 1 and s[0] == '?':\n",
    "            return 'a'\n",
    "\n",
    "        ls = list(s)\n",
    "        for i in range(n):\n",
    "            if ls[i] == '?':\n",
    "                for j in letters:\n",
    "                    if i == 0:\n",
    "                        if j != ls[i + 1]:\n",
    "                            ls[i] = j\n",
    "                    elif i == n - 1:\n",
    "                        if j != ls[i - 1]:\n",
    "                            ls[i] = j\n",
    "                    else:\n",
    "                        if j != ls[i - 1] and j != ls[i + 1]:\n",
    "                            ls[i] = j\n",
    "        return \"\".join(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        res = list(s)\n",
    "        n=len(res)\n",
    "        for i in range(n):\n",
    "            if res[i]=='?':\n",
    "                for b in \"abc\":\n",
    "                    if not (i>0 and res[i-1]==b or i<n-1 and res[i+1]==b):\n",
    "                        res[i]=b\n",
    "                        break\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        l = list(s)\n",
    "        for i, c in enumerate(l):\n",
    "            if c == '?':\n",
    "                temp = ''\n",
    "                if i > 0:\n",
    "                    temp += l[i-1]\n",
    "                if i < len(l) - 1:\n",
    "                    temp += l[i+1]\n",
    "                l[i] = next(c for c in 'abc' if c not in temp)\n",
    "        return ''.join(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n==1:\n",
    "            return s if s[0]!='?'else 'a'\n",
    "\n",
    "        ls = list(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == '?':\n",
    "                for ch in 'abc':\n",
    "                    if not (i>0 and ls[i-1]==ch or i<n-1 and ls[i+1]==ch):\n",
    "                        ls[i] = ch\n",
    "                        break\n",
    "        return ''.join(ls)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        ans = ''\n",
    "        for i, c in enumerate(s):\n",
    "            if c=='?':\n",
    "                c = list(set(string.ascii_lowercase) - set(ans[i-1] if i - 1>=0 else '') - set(s[i+1] if i + 1 <len(s) else ''))[0]\n",
    "            ans += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        \n",
    "        arr = list(s)\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            curr = arr[i]\n",
    "            if curr != \"?\":\n",
    "                continue\n",
    "            for sub in \"abc\":\n",
    "                if i > 0 and arr[i - 1] == sub:\n",
    "                    continue\n",
    "                if i < len(s) - 1 and arr[i + 1] == sub:\n",
    "                    continue\n",
    "                arr[i] = sub\n",
    "        \n",
    "        return \"\".join(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        letters = 'abc'\n",
    "\n",
    "        if n == 1 and s[0] == '?':\n",
    "            return 'a'\n",
    "\n",
    "        ls = list(s)\n",
    "        for i in range(n):\n",
    "            if ls[i] == '?':\n",
    "                for j in letters:\n",
    "                    if i == 0:\n",
    "                        if j != ls[i + 1]:\n",
    "                            ls[i] = j\n",
    "                    elif i == n - 1:\n",
    "                        if j != ls[i - 1]:\n",
    "                            ls[i] = j\n",
    "                    else:\n",
    "                        if j != ls[i - 1] and j != ls[i + 1]:\n",
    "                            ls[i] = j\n",
    "        return \"\".join(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        if len(s)==1:\n",
    "            if s[0] != \"?\":\n",
    "                return s\n",
    "            else:\n",
    "                return 'a'\n",
    "        if s[0]==\"?\":\n",
    "            if s[1]==\"?\":\n",
    "                new = 'a'\n",
    "            else:\n",
    "\n",
    "                tempnum = (ord(s[1])+1)%122\n",
    "                if tempnum <98:\n",
    "                    tempnum += 98\n",
    "                new = chr(tempnum)\n",
    "    \n",
    "\n",
    "        else:\n",
    "            new = s[0]\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i] != \"?\" and s[i]!=new[i-1]:\n",
    "                new += s[i]\n",
    "                print(\"sdf\",new)\n",
    "            else:\n",
    "                tempnum = (ord(new[-1])+1)%122\n",
    "                if tempnum <98:\n",
    "                    tempnum += 98\n",
    "                temp = chr(tempnum)\n",
    "              \n",
    "                \n",
    "                if temp == s[i+1]:\n",
    "                    temp = chr(ord(temp)+1)\n",
    "                new += temp\n",
    "                print(new)\n",
    "        if s[-1]==\"?\":\n",
    "            if new[-1] != 'a':\n",
    "                new +=  'a'\n",
    "            else:\n",
    "                new +='b'\n",
    "        else:\n",
    "            new += s[-1]\n",
    "        return new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        ret = ''\n",
    "        for i in range(n):\n",
    "            if s[i] != '?':\n",
    "                ret += s[i]\n",
    "            else:\n",
    "                exists = ''\n",
    "                if ret:\n",
    "                    exists += ret[-1]\n",
    "                if i + 1 < n and s[i+1] != '?':\n",
    "                    exists += s[i+1]\n",
    "                for c in 'abc':\n",
    "                    if c not in exists:\n",
    "                        ret += c\n",
    "                        break\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "alphabets = set(list('abcdefghijklmnopqrstuvwxyz'))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i] == '?':\n",
    "                exclude = set()\n",
    "                if i - 1 >= 0:\n",
    "                    exclude.add(s[i-1])\n",
    "                if i + 1 < length:\n",
    "                    exclude.add(s[i+1])\n",
    "                print(exclude)\n",
    "                if i + 1 < length:\n",
    "                    s = s[:i] + (alphabets - exclude).pop() + s[i + 1:]\n",
    "                else:\n",
    "                    s = s[:i] + (alphabets - exclude).pop()\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        letters = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "        if n == 1 and s[0] == '?':\n",
    "            return 'a'\n",
    "\n",
    "        ls = list(s)\n",
    "        for i in range(n):\n",
    "            if ls[i] == '?':\n",
    "                for j in letters:\n",
    "                    if i == 0:\n",
    "                        if j != ls[i + 1]:\n",
    "                            ls[i] = j\n",
    "                    elif i == n - 1:\n",
    "                        if j != ls[i - 1]:\n",
    "                            ls[i] = j\n",
    "                    else:\n",
    "                        if j != ls[i - 1] and j != ls[i + 1]:\n",
    "                            ls[i] = j\n",
    "        return \"\".join(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s1= 'abcdefghijklmnopqrstuvwxyz'\n",
    "        res = list('0'+s+'0')\n",
    "        i=1       \n",
    "        while i<len(res)-1:\n",
    "            if res[i]=='?':\n",
    "                j=0\n",
    "                while j<len(s1):\n",
    "                    if s1[j] not in [res[i-1],res[i+1]]:\n",
    "                        res[i]=s1[j]\n",
    "                        break\n",
    "                    j+=1\n",
    "            i+=1\n",
    "        return ''.join(res[1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        res = list(s)\n",
    "        for i in range(n):\n",
    "            if res[i] == '?':\n",
    "                for char in 'abc':\n",
    "                    if not (i > 0 and res[i-1] == char or i < n-1 and res[i+1] == char):\n",
    "                        res[i] = char\n",
    "                        break\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n==1:\n",
    "            return s if s[0]!='?'else 'a'\n",
    "\n",
    "        ls = list(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == '?':\n",
    "                for ch in 'abc':\n",
    "                    if i == 0 :\n",
    "                        if ls[i+1]!=ch:\n",
    "                            ls[i] = ch\n",
    "                            break\n",
    "                    elif i==n-1:\n",
    "                        if ls[i-1]!=ch:\n",
    "                            ls[i] = ch\n",
    "                            break\n",
    "                    else:\n",
    "                        if ls[i-1]!=ch and ls[i+1]!=ch:\n",
    "                            ls[i] = ch\n",
    "                            break\n",
    "        return ''.join(ls)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "题目要求将字符串 sss 中的 ‘?’\\texttt{`?'}‘?’ 转换为若干小写字母，转换后的字母与该字母的前后字母均不相同。遍历字符串 sss，如果遇到第 iii 个字符 s[i]s[i]s[i] 为 ‘?’\\texttt{`?'}‘?’ 时，此时直接在英文字母 ‘a’-‘z’\\texttt{`a'-`z'}‘a’-‘z’ 中找到一个与 s[i−1]s[i-1]s[i−1] 和 s[i+1]s[i+1]s[i+1] 均不相同的字母进行替换即可。\n",
    "\n",
    "在替换时，实际不需要遍历所有的小写字母，只需要遍历三个互不相同的字母，就能保证一定找到一个与前后字符均不相同的字母，在此我们可以限定三个不同的字母为 (‘a’,‘b’,‘c’)\\texttt{(`a',`b',`c')}(‘a’,‘b’,‘c’)。\n",
    "\n",
    "    '''\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        res=list(s)\n",
    "        n=len(res)\n",
    "        for i in range(n):\n",
    "            if res[i]==\"?\":\n",
    "                for b in \"abc\":\n",
    "                    if not (i>0 and res[i-1]==b or i<n-1 and res[i+1]==b):\n",
    "                        res[i]=b\n",
    "                        break\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        letters_set = set(string.ascii_lowercase)\n",
    "\n",
    "        s = ['']+list(s)+['']\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i] == '?':\n",
    "                s[i] = random.choice(list(letters_set - set([s[i-1],s[i+1]])))\n",
    "\n",
    "        return ''.join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        # 多种情况判断\n",
    "        if s == \"?\":\n",
    "            return \"b\"\n",
    "\n",
    "        def exchange(x, y=\"a\"):\n",
    "            ox, oy = ord(x), ord(y)\n",
    "            for nu in range(97, 123):\n",
    "                if nu != ox and nu != oy:\n",
    "                    return chr(nu)\n",
    "        \n",
    "        res = \"\"\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"?\":\n",
    "                if i == 0:\n",
    "                    ch = exchange(s[1])\n",
    "                elif i == len(s)-1:\n",
    "                    ch = exchange(res[-1])\n",
    "                else:\n",
    "                    ch = exchange(res[-1], s[i+1])\n",
    "            res += ch \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '?':\n",
    "                if i == 0 and i != len(s)-1:\n",
    "                    for j in range(ord('a'),ord('c')):\n",
    "                        if chr(j) != s[i+1]:\n",
    "                            s = chr(j)+s[i+1:]\n",
    "                elif i == 0 and i == len(s)-1:\n",
    "                    return 'a'\n",
    "                elif i > 0 and i != len(s)-1:\n",
    "                    for j in range(ord('a'),ord('z')):\n",
    "                        if chr(j)!=s[i+1] and chr(j)!=s[i-1]:\n",
    "                            s = s[:i]+chr(j)+s[i+1:]\n",
    "                elif i > 0 and i == len(s)-1:\n",
    "                    for j in range(ord('a'),ord('z')):\n",
    "                        if chr(j) != s[i-1]:\n",
    "                            s = s[:i]+chr(j)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "      ans = []\n",
    "      for i in range(len(s)):\n",
    "        if s[i] == \"?\":\n",
    "          for j in range(26):\n",
    "            ch = ord(\"a\") + j\n",
    "            if ans and ch == ord(ans[-1]):\n",
    "              continue\n",
    "            if i < len(s) - 1 and ch == ord(s[i+1]):\n",
    "              continue\n",
    "            ans.append(chr(ch))\n",
    "            break\n",
    "        else:\n",
    "          ans.append(s[i])\n",
    "      return ans\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        if s == '?':\n",
    "            return 'a'\n",
    "        s = [x for x in s]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '?':\n",
    "                if i == 0:\n",
    "                    for num in range(97,123):\n",
    "                        if chr(num) != s[i+1]:\n",
    "                            s[0] = chr(num)\n",
    "                            break\n",
    "                elif i == len(s)-1:\n",
    "                    for num in range(97,123):\n",
    "                        if chr(num) != s[i-1]:\n",
    "                            s[i] = chr(num)\n",
    "                            break\n",
    "                else:\n",
    "                    for num in range(97,123):\n",
    "                        if chr(num) != s[i-1] and chr(num) != s[i+1]:\n",
    "                            s[i] = chr(num)\n",
    "                            break\n",
    "        return ''.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s = '#' + s + '#'\n",
    "        s = list(s)\n",
    "        for i,char in enumerate(s):\n",
    "            if char == '?':\n",
    "                if s[i-1] == 'a' or s[i+1] == 'a':\n",
    "                    if s[i-1] == 'b' or s[i+1] == 'b':s[i] = 'c'\n",
    "                    else:s[i] = 'b'\n",
    "                else:\n",
    "                    s[i] = 'a'\n",
    "        return ''.join(s).replace('#','')\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        res = list(s)\n",
    "        n = len(res)\n",
    "        for i in range(n):\n",
    "            if res[i] == '?':\n",
    "                for b in \"abc\":\n",
    "                    if not (i > 0 and res[i - 1] == b or i < n - 1 and res[i + 1] == b):\n",
    "                        res[i] = b\n",
    "                        break\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        letter = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        res = list('#'+s+'#') # 首尾加入哨兵，将首尾为‘？’的特殊情况也变成一般情况\n",
    "        for p in range(1,len(res)-1):\n",
    "            if res[p]=='?':\n",
    "                for c in letter:\n",
    "                    if c != res[p-1] and c != res[p+1]:\n",
    "                        res[p]=c\n",
    "        return ''.join(res[1:-1]) # 对res切片，去掉首尾两个哨兵\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "            ab = set(string.ascii_lowercase)\n",
    "            char = \"?\"\n",
    "            m: Dict[int, str] = {}\n",
    "            l = list(s)\n",
    "            for i, letter in enumerate(l):\n",
    "                if letter == char:\n",
    "                    \n",
    "                    if i == len(s) - 1:\n",
    "                        invalid_c = {s[i - 1]}\n",
    "                    elif i == 0:\n",
    "                        invalid_c = {s[i + 1]}\n",
    "                    else:\n",
    "                        invalid_c = {s[i - 1], s[i + 1]}\n",
    "                    if m.get(i-1):\n",
    "                        invalid_c.add(m[i-1])\n",
    "\n",
    "                    m[i] = (ab - (invalid_c - {char})).pop()\n",
    "                    print(m[i],invalid_c)\n",
    "                    l[i] = m[i]\n",
    "            return \"\".join(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "alphabets = set(list('abcdefghijklmnopqrstuvwxyz'))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i] == '?':\n",
    "                exclude = set()\n",
    "                if (pre := i - 1) >= 0:\n",
    "                    exclude.add(s[pre])\n",
    "                if (follow := i + 1) < length:\n",
    "                    exclude.add(s[follow])\n",
    "                print(exclude)\n",
    "                if i + 1 < length:\n",
    "                    s = s[:i] + (alphabets - exclude).pop() + s[i + 1:]\n",
    "                else:\n",
    "                    s = s[:i] + (alphabets - exclude).pop()\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) - 1):\n",
    "            if s[i] != '?':\n",
    "                continue\n",
    "            for k in range(ord('a'), ord('z') + 1):\n",
    "                # print(k,chr(k), chr(k) != s[i - 1], chr(k) != s[i + 1])\n",
    "                if chr(k) != s[i - 1] and chr(k) != s[i + 1]:\n",
    "                    s[i] = chr(k)\n",
    "                    break\n",
    "        if s[-1] == '?':\n",
    "            if len(s) > 1:\n",
    "                for k in range(ord('a'), ord('z') + 1):\n",
    "                    if chr(k) != s[-2]:\n",
    "                        s[-1] = chr(k)\n",
    "            else:\n",
    "                s = 'a'\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        a = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        for i, v in enumerate(s):\n",
    "            if v == '?':\n",
    "                for j in a:\n",
    "                    b = s[0: i+2] if i == 0 else s[i-1: i+2]\n",
    "                    if j not in b:\n",
    "                        s[i] = j\n",
    "                        break\n",
    "        return ''.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"?\":\n",
    "                if i == 0:\n",
    "                    for char in range(ord(\"a\"),ord(\"z\")):\n",
    "                        if i+1<len(s) and chr(char) !=s[i+1]:\n",
    "                            s[i] = chr(char)\n",
    "                        elif i+1>=len(s):\n",
    "                            s[i] = \"a\"\n",
    "                elif i == len(s)-1:\n",
    "                    for char in range(ord(\"a\"),ord(\"z\")):\n",
    "                        if chr(char) != s[i-1]:\n",
    "                            s[i] = chr(char)\n",
    "                else:\n",
    "                    for char in range(ord(\"a\"),ord(\"z\")):\n",
    "                        if chr(char) != s[i-1] and chr(char) != s[i+1]:\n",
    "                            s[i] = chr(char)\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifyString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        letters = 'abc'\n",
    "\n",
    "        if n == 1 and s[0] == '?':\n",
    "            return 'a'\n",
    "\n",
    "        ls = list(s)\n",
    "        for i in range(n):\n",
    "            if ls[i] == '?':\n",
    "                for j in letters:\n",
    "                    if i == 0:\n",
    "                        if j != ls[i + 1]:\n",
    "                            ls[i] = j\n",
    "                    elif i == n - 1:\n",
    "                        if j != ls[i - 1]:\n",
    "                            ls[i] = j\n",
    "                    else:\n",
    "                        if j != ls[i - 1] and j != ls[i + 1]:\n",
    "                            ls[i] = j\n",
    "        return \"\".join(ls)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
